package bTree.LeetCode;

import java.util.ArrayList;
import java.util.List;

public class 无重复字符串的排列组合 {
    public String[] permutation(String S) {
        List<String> list = new ArrayList<>();
        int length = S.length();
        boolean[]visited=new boolean[length];
        StringBuilder sb=new StringBuilder();
        troll(S, list,visited,sb);
        int size = list.size();
        String[]strings=new String[size];
        for (int i = 0; i < list.size(); i++) {
            strings[i]=list.get(i);
        }
        return strings;
    }

    private void troll(String s, List<String> list, boolean[] visited, StringBuilder sb) {
        if (sb.length()==s.length()){
            list.add(sb.toString());
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (!visited[i]){
                sb.append(s.charAt(i));
                visited[i]=true;
                troll(s, list,visited,sb);
                sb.deleteCharAt(sb.length()-1);
                visited[i]=false;
            }
        }
    }
}